Beyond Descriptive Modelling of Network Degrees: Tail-Realistic Preferential Attachment
October 31, 2025
Networks
Networks are everywhere
Fairly simple and can represent complex systems
Objects represented by the nodes
Relationships represented by edges
Key feature is the degree
Each node has in/out-degree representing the number of incoming and outgoing edges
Examples
Instagram
Flights
Protein Interactions
Citations
CRAN
1
3
0
2
3
1
3
1
2
4
0
2
5
0
2
Network Data
Rarely have full temporal data, usually only a snapshot
Full evolution is too constly or impossible to observe
We often instead choose to study properties of these snapshots
e.g. the degrees
Often unavailable or too costly to extract
Contains a lot of information \(~\)
More often available
Much easier to work with
Can still study key properties e.g. degrees
The scale-free debate
A lot of discussion over the shape of real degree distributions
Many claim a lot of real networks are “scale-free”
Others disagree, claiming unrealistic expectations
Literature doesn’t even agree on the definition of scale-free
We will be using the most general definition, regular variation
There has been a heated debate over the presence of scale-free networks in reality.
Scale-free Degree Distribution — Orginal scale
Scale-free Degree Distribution — Log scale
Several definitions of scale-free in the literature
Heavier than exponential
\[
\bar F (k) \gg e^{-ck}
\]
Power-law \[
\bar F(k) \sim k^{-\gamma}
\]
Regularly varying tail \[
\bar F(k) = k^{-\gamma}\mathcal L (k)
\]
Modelling the degrees
Power Law
\[
K\sim \text{Pareto}(\gamma)
\] \[
~
\] Estimate \(\gamma\)
Tail Estimation
\[
K|K>u \sim \text{GP}(\xi, \sigma)
\] \[
~
\] Estimate \((\xi,\sigma)\)
Piecewise Model
\[
K|K< u \sim \text{Pareto}(\gamma)
\] \[
K|K>u \sim \text{GP}(\xi, \sigma)
\] Estimate \((\gamma, u, \xi, \sigma)\)
Discrete Piecewise Model
This model, used by Clement and some collaborators
Uses something like a power law for the body but with some added flexibility
\(\theta\) measures how straight the line is i.e. how close to power-law the body is
Uses a discretisation of the GP for the tail
Zipf-Polylog
\[
f(k) \propto k^{-\alpha} \theta^k, \qquad k=1, 2, \ldots, u
\]
Integer Generalised Pareto
\[
F(k)= 1-\left(1+\frac{\xi(k-u)}{\sigma +\xi u}\right)_+^{-1/\xi}, \qquad k=u+1,\ldots
\]
Using this model Lee, Eastoe, and Farrell (2024 ) found that networks often have a heavy tail but not quite as heavy as implied by the body.
Why care about scale-freeness?
Why this obsession with scale-freeness and power-laws
People jump from ‘looks like a power law’ to claiming preferential attachment
This only works one way PA -> power law not the other way round
Other than these claims the modelling of degrees is usually descriptive
We learn nothing about how the network grew.
Many use scale-freeness of a network to justify the mechanics behind the network’s growth.
Preferential Attachment (rich-get-richer) \(\Rightarrow\) Power-law degree distribution
but
Power-law degree distribution \(\nRightarrow\) Preferential Attachment (rich-get-richer)
This is fairly common as modelling the degrees does not generally inform the network growth.
Preferential Attachment
Now lets take a look at that preferential attachment model so many love to claim - Usually called the Barabasi-Albert model or Yule-Simon - Features a rich-get-richer mechanism - The higher your degree the more likely you are to get more connections
This produces a power law with exponent 2, explaining why so many people like to claim a power law so they can use this model
However, in reality the behaviour of degree distributions is much more nuanced
We look to make this model more general
Steps
Node added to network
Connects to \(m\) existing nodes with weights \(\pi_i\) :
\[
\pi_i = \left. k_i \middle/ \sum_j k_j \right.
\] where \(k_i\) is degree of node \(i\) .
Results in a power-law degree distribution
\[
\bar F(k)\sim k^{-2}
\]
General Preferential Attachment
We make it more general by simply changing the \(k+1\) to be instead a general function of the in-degree.
This should allow for much more flexible behaviour that can potentially match that of real networks
But, how do we study this given how general it is
Steps
Node added to network
Connects to \(m\) existing nodes with weights \(\pi_i\) :
\[
\pi_i = \left. b(k_i) \middle/ \sum_j b(k_j) \right.
\] where \(k_i\) is degree of node \(i\) .
How do we study the degree distribution of this?
Aims
Connect preference function to tail behaviour of limiting degree distribution
Propose a flexible tail-realistic model for networks degrees
Obtain information about network growth from degrees alone of real data
Starting with a branching process
Consider the GPA model when \(m=1\) , and a continuous time branching process \(\zeta(t)\) where:
\(\zeta(0)=0\) \(\zeta(t)\) driven by Markovian pure birth
\[
\Pr(\zeta(t+\text{d}t) = k+1 | \zeta(t) =k) = b(k) \text{d}t + o(\text{d}t)
\]
This pure birth process corresponds to the growth of an individual nodes degree.
Equivalence to GPA
Construct the tree \(\Upsilon(t)\) determined by \(\zeta(t)\) such that:
\(\Upsilon(0)=\left\{\emptyset\right\}\) Each node, \(x\) , in \(\Upsilon(t)\) gives birth at rate \(b(\text{deg}(x, \Upsilon(t)))\)
Denote \(\Upsilon(t)_{\downarrow x}\) the tree when treating \(x\) as the root.
This construction is equivalent to the GPA model with \(m=1\) and preference function \(b(\cdot)\)
A limiting result
Rudas studied this and with results from CTBP established the following result - for some characeteristic function, phi, we have that - where rho hat is the laplace transform of the density of the point process associated with the CTBP
Rudas, Tóth, and Valkó (2007 ) states that for a given characteristc function \(\phi(\cdot)\)
\[
\lim_{t\rightarrow\infty} \frac{1}{\left|\Upsilon(t)\right|}\sum_{x\in\Upsilon(t)}\phi(\Upsilon(t)_{\downarrow x}) = \lambda^* \int_0^\infty e^{-\lambda^*}\mathbb E \left[\phi(\Upsilon(t))\right]\text{d}t
\]
where \(\lambda^*\) satisfies
\[
\hat\rho(\lambda^*) = \int_0^\infty e^{-\lambda^*t}\rho(t)\text{d}t = 1
\]
and \(\rho(t)\) is the density of the point process associated with \(\zeta(t)\) .
Getting the degree distribution
Using the fact that we can write the empirical tail of the degrees as - In the limit of time going to infinity this empirical distribution we can get the tail of the limiting degree distribution
This gets us quite an elegant form, which looks fairly simple
how do we study this
We can write the tail of the degree distribution at time \(t\) as:
\[
\frac{\sum_{x\in\Upsilon(t)} \mathbb I\left\{\text{deg}(x, \Upsilon(t)\downarrow x)>k \right\} }{\left|\Upsilon(t)\right|}
\]
and so the tail of the limiting degree distribution as \(t\rightarrow \infty\) is:
\[
\bar F(k) = \lim_{t\rightarrow\infty} \frac{\sum_{x\in\Upsilon(t)} \mathbb I\left\{\text{deg}(x, \Upsilon(t)_{\downarrow x})>k \right\} }{\left|\Upsilon(t)\right|}
\]
So we can now use the previous result to obtain:
\[
\bar F(k) = \lambda^* \int_0^\infty e^{-\lambda^*t}\mathbb E\left[\mathbb I\left\{\text{deg}(x, \Upsilon(t)_{\downarrow x})>k \right\}\right]\text{d}x
\]
Through fairly simple calculations we get:
\[
\bar F(k) = \prod_{i=0}^k\frac{b(i)}{\lambda^*+b(i)}
\]
where \(\lambda^*\) satisfies
\[
\hat \rho(\lambda^*) = \sum_{k=0}^\infty \prod_{i=0}^k\frac{b(i)}{\lambda^* + b(i)} = 1
\]
What effect does \(b(\cdot)\) have on this degree distribution, particularly in the tail?
Studying the tail
We would like to pay close attention to the largest degrees as in many networks these happen to be very influential - The perfect application of extreme value theory
Often people will just use continuous methods to study these dergee distributions either by assuming they will just work - or adding a jiggle to the points and then applying the continuous methods
We want to be more precise and use machinery made for discrete data
We want to pay careful attention to the extreme values
Studies of empirical degrees often use methods from continuous extremes
As this is a discrete distribution we need some new machinery.
Continuous Extremes Recap
Maximum Domains of Attraction (MDA)
Frechet (heavy tailed)
\[
\bar F(x) = x^{-\gamma} \mathcal L(x)
\] e.g. Pareto, Cauchy, Lévy
Gumbel (light-tailed)
\[
\lim_{x\rightarrow\infty}\frac{\bar F (x + t a(x))}{\bar F(x)}= e^{-t}
\] e.g. Exponential, Normal, Gamma
The Frechet is equivalent to regular variation with tail-index \(\gamma\)
Power-law falls into the Frechet MDA with \(\mathcal L(x)=1\)
All continuous distributions with infinite right endpoint fall into one of these.
Many discrete distributions don’t satisfy the conditions to belong to an MDA
Discrete Extremes
Shimura (2012 ) uses the following quantity to categorise discrete distributions \[
\Omega(F, k) = \left(\log \frac{\bar F(k+1)}{ \bar F(k+2)}\right)^{-1} - \left(\log \frac{\bar F(k)}{ \bar F(k+1)}\right)^{-1}
\]
Frechet
\[
\lim_{k\rightarrow\infty} \Omega(F,k) = 1/\alpha
\] and \[
\lim_{k\rightarrow\infty} \frac{\bar F(k+1)}{\bar F(k)} = 1
\]
Gumbel
\[
\lim_{k\rightarrow\infty} \Omega(F,k) = 0
\] and \[
\lim_{k\rightarrow\infty} \frac{\bar F(k+1)}{\bar F(k)} = 1
\]
Recoverable to Gumbel
\[
\lim_{k\rightarrow\infty} \Omega(F,k) = 0
\] and \[
\lim_{k\rightarrow\infty} \frac{\bar F(k+1)}{\bar F(k)} \neq 1
\]
Analysing GPA degrees
Plugging in the limitng survival from earlier can an show that:
Provided the preference is unbounded
falls in the Frechet if and only if “eventually linear”
falls into the Gumbel if and only if this limit goes to zero
If it is indeed bounded then it falls into neither but is recoverable to the Gumbel
i.e. it is close to being in the Gumbel
Examples
We look at three possible simple forms of preference function - The first we have seen before and know how it behaves, we can see that this agrees
Now we can use the limiting survival function of a GPA model to show that:
\[
\lim_{k\rightarrow\infty} \Omega(F,k)= \begin{cases} \lim_{k\rightarrow \infty}\frac{b(k+1)-b(k)}{\lambda^*}, &\text{when } b(k) \rightarrow \infty\\
0, &\text{otherwise}
\end{cases}
\]
and therefore for \(b(k)\rightarrow\infty\) as \(k\rightarrow\infty\)
\(\bar F (k)\) is regularly varying (Frechet MDA ) if and only if \(\lim_{k\rightarrow \infty}[b(k+1)-b(k)] = \nu >0\) , in which case the tail index is \(\lambda^*/\nu\) \(\bar F(k)\) is light-tailed (Gumbel MDA ) if and only if \(\lim_{k\rightarrow \infty}[b(k+1)-b(k)]=0\) .
Note that if \(\lim_{k\rightarrow\infty} b(k)<\infty\) , then \(\bar F(k)\) is recoverable to the Gumbel MDA.
Examples
Barabasi-Albert (BA) \[
b(k) = k+1
\]
\[
\lim_{k\rightarrow\infty} \Omega(F,k) = 1/\lambda^* = 1/2
\] \[
\lim_{k\rightarrow\infty} \frac{\bar F(k+1)}{\bar F(k)} = 1
\] Frechet, with index 2
Polynomial \[
b(k) = (k+1)^\alpha, \quad \alpha\in (0,1)
\]
\[
\lim_{k\rightarrow\infty} \Omega(F,k) = 0
\] \[
\lim_{k\rightarrow\infty} \frac{\bar F(k+1)}{\bar F(k)} = 1
\] Gumbel
Uniform \[
b(k) = c, \quad c>0
\]
\[
\lim_{k\rightarrow\infty} \Omega(F,k) = 0
\] \[
\lim_{k\rightarrow\infty} \frac{\bar F(k+1)}{\bar F(k)} \neq 0
\] Recoverable to Gumbel
What we have learned so far.
Main result
\(\bar F (k)\) is regularly varying (Frechet MDA ) if and only if \(\lim_{k\rightarrow \infty}[b(k+1)-b(k)] = \nu >0\) , in which case the tail index is \(\lambda^*/\nu\) \(\bar F(k)\) is light-tailed (Gumbel MDA ) if and only if \(\lim_{k\rightarrow \infty}[b(k+1)-b(k)]=0\) .
For degree distribution to be heavy tailed and be the result of a GPA model, preference must be eventually “linear” like in the BA model
Empirical degree distributions are heavy-tailed but exhibit more nuanced behaviour than obtained by BA model
Constructing a new preference function
So clearly we need to move beyond the standard preferential attachment or BA model - Inspired by the piecewise model from earlier which showed promising results for modelling empirical degrees
We propose a piecewise preference function that - Incorporates the polynomial behaviour from earlier - But is guaranteed the be linear in the limit
We require something that is eventually linear but is flexible enough for real networks
Barabasi-Albert \[
b(k) = k+1
\]
Proposed Model \[
b(k) = \begin{cases}
k^\alpha + \varepsilon, &k\le k_0\\
k_0^\alpha + \varepsilon + \beta(k-k_0), &k>k_0
\end{cases}
\]
\[
\bar F(k) = \frac{2}{(k+2)(k+3)}
\]
\[
\bar F(k) = \begin{cases}
\prod_{i=0}^{k}\frac{i^\alpha + \varepsilon}{\lambda^*+i^\alpha + \varepsilon},&k\le k_0,\\
\left(\prod_{i=0}^{k_0-1}\frac{i^\alpha + \varepsilon}{\lambda^*+i^\alpha + \varepsilon}\right)\frac{\Gamma(\lambda^*+k_0^\alpha + \varepsilon)/\beta)}{\Gamma\left((k_0^\alpha + \varepsilon)/\beta\right)} \frac{\Gamma\left(k-k_0 + 1 +\frac{k_0^\alpha + \varepsilon}{\beta}\right)}{\Gamma\left(k-k_0 + 1 +\frac{\lambda^* +k_0^\alpha + \varepsilon}{\beta}\right)},&k > k_0,
\end{cases}
\]
Shape of degree distribution
Shown here are some examples of the shape of distributions from the model with various parameter choices
All guaranteed to be in the Frechet, aligning with resultsf from Lee, Eastoe, and Farrell (2024 )
Tail behaviour
Here are some heatmaps of the tail indices for various parameter choices and how they change with respect to (,) - the red line indicates those parameter choices that give the same tail index as the BA model
All limiting degree distributions produced by this model are Frechet with tail-index \(\lambda^*/\beta\) .
Simulation Study - set up
Simulate networks
Use likelihood to fit model
Recover parameters
The simulated data
100,000 nodes
36 parameter combinations
\(k_0\) fixed at \(20\) Only using final degrees
The likelihood
\[
\begin{aligned}
L(\pmb n | \pmb \theta,l) = &\left(\frac{\lambda^*}{\lambda^*+\varepsilon}\right)^{n_0}\left(\prod_{j=l}^{k_0-1}\frac{j^\alpha +\varepsilon}{\lambda^* + j^\alpha +\varepsilon}\right)^{\left(\sum_{i\ge k_0}n_{i}\right)} \\ &\times \prod_{l \le i<k_0}\left(\frac{\lambda^*}{\lambda^* +i^\alpha + \varepsilon } \prod_{j=l}^{k_0-1}\frac{j^\alpha + \varepsilon}{\lambda^* + j^\alpha + \varepsilon}\right)^{n_i}\\ &\times \prod_{i\ge k_0}\left(\frac{\text{B}(i-k_0 + (k_0^\alpha + \varepsilon)/\beta,1+\lambda^*/\beta)}{\text{B}((k_0^\alpha + \varepsilon)/\beta,\lambda^*/\beta)}\right)^{n_i},
\end{aligned}
\]
Priors
\[\begin{align*}
\alpha&\sim \text{Gamma}(1,0.01),\\
\beta &\sim \text{Gamma}(1,0.01),\\
k_0 &\sim \text{U}(1,10,000),\\
\varepsilon &\sim \text{Gamma(1,0.01)},
\end{align*}\]
Now we use an adaptive Metropolis-Hastings to obtain posterior samples
Model fits
The results
In the following slides we show that the model parameters are recovered well from the degrees - In most cases highly concentrated around the true values - Cases where they are not are either because the threshold value is not reached in the simulation or an identifiability issue - alpha=beta=1 can identify the threshold or it goes to zero/max(data) and alpha/beta becomes a free parameter
Posterior of \(\alpha\)
The results
Posterior of \(\varepsilon\)
The results
Posterior of \(k_0\)
The results
Posterior of \(\beta\)
Real Data
Given the promising results from the sim study showing that parameters can be recovered from the degrees alone - we now apply to empirical networks
We compare the performance of this model to that of the discrete pw model.
95% CI of survival function
we can see that the model performs similarly and sometimes better than the pw model and captures the tail especially well
95% CI of preference function
But we know now that by fitting this model we not only model the degree distribution - We are also getting estimates for the model parameters and therefore the preference function - The credible intervals are quite large but it is more information that simply the pw model
Interpretation
Levelling off may suggest diminishing returns behaviour
Internet seems to be essentially a linear function and any gain in number of connections gives the same benefit no matter what
This lines up with existing literature on the structure of the internet.
Key Results
Characterisation of degree distribution from preference function
Eventually linear \(\rightarrow\) Frechet (heavy tail)
Sublinear and unbounded \(\rightarrow\) Gumbel (light tail)
Bounded \(\rightarrow\) recoverable to Gumbel (light tail)
Proposed preference function gives tail-realistic degree distributions
Parameters recovered from degrees alone in simulated networks
Can learn about real networks growth from snapshot of degrees
Limitations and Future work
Theory based on trees, which real networks rarely are
Only consider degrees in the snapshot
Assume a fairly restrictive model (pure birth)
Look beyond just the degrees
Incorporate more complex behaviour into the growth model
Extend theory beyond that of trees
